package medium

import "sort"

/*
时间复杂度:O(NlogN)
空间复杂度:O(N) 存储每辆车初始时计算出的到达目的地的时间

f1:排序
f2:排序+单调栈
*/

func carFleet(target int, position []int, speed []int) int {
	cars := make([][2]int, len(position))
	for i, v := range position {
		cars[i] = [2]int{v, speed[i]}
	}
	// 题目说明了一开始所有车的位置都不相同
	sort.Slice(cars, func(i, j int) bool {
		return cars[i][0] < cars[j][0]
	})
	times := make([]float64, 0)
	// 计算每辆车到达target的时间
	for _, v := range cars {
		times = append(times, float64(target-v[0])/float64(v[1]))
	}

	// times中存储的是按照位置排序后,每辆车达到target的时间,当存在2辆及2辆车以上时,就从前到后对相邻的车进行比较
	// 如果后面一辆车到达target的时间要小于等于前面一辆车,则说明后面的车肯定能在<=target时追上前面那辆车,否则肯定追不上,即无法组成一个车队
	// 最前面那辆车只能单独开到终点: ans++
	//
	// 这里需要注意一点:由于后面的车如果能追上前面的车,则说明后面车速度比前面车快,一但追上了,则跟前面那辆车合并,速度变成前面那辆车的速度,
	// 其最终到达终点的时间,是取决于前面那辆车的!!!
	//
	// 这里利用单调栈来处理也是可以的,从后往前遍历times,如果前面的time>=栈顶元素,则说明,后面的车能追上前面的车,将栈顶元素弹出,然后入栈,
	// 最后计算栈中总共有多少元素即可
	ans := 0
	for len(times) > 1 {
		lead := times[len(times)-1]
		times = times[:len(times)-1]
		// 后面的车永远追不上
		if lead < times[len(times)-1] {
			ans++
		} else {
			// 如果能在<=target时追上,则后面的车到达终点的时间,取决于前面那辆车
			times[len(times)-1] = lead
		}
	}
	return ans + len(times)
}
